The approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
In computer networks such as the Internet, packets of data are sent from a source to a destination via a network of elements including links (communication paths such as telephone or optical lines) and nodes (for example, routers directing the packet along one or more of a plurality of links connected to it) according to one of various routing protocols.
One class of routing protocol is the link state protocol. The link state protocol relies on a routing algorithm resident at each node. Each node on the network advertises, throughout the network, links to neighboring nodes and provides a cost associated with each link, which can be based on any appropriate metric such as link bandwidth or delay and is typically expressed as an integer value. A link may have an asymmetric cost, that is, the cost in the direction AB along a link may be different from the cost in a direction BA. Based on the advertised information in the form of a link state packet (LSP) each node constructs a link state database (LSDB), which is a map of the entire network topology, and from that constructs generally a single optimum route to each available node based on an appropriate algorithm such as, for example, a shortest path first (SPF) algorithm. As a result a “spanning tree” (SPT) is constructed, rooted at the node and showing an optimum path including intermediate nodes to each available destination node. The results of the SPF are stored in a routing information base (RIB) and based on these results the forwarding information base (FIB) or forwarding table is updated to control forwarding of packets appropriately. When there is a network change an LSP representing the change is flooded through the network by each node adjacent the change, each node receiving the LSP sending it to each adjacent node.
As a result, when a data packet for a destination node arrives at a node the node identifies the optimum route to that destination and forwards the packet to the next node along that route. The next node repeats this step and so forth.
It will be noted that in normal forwarding each node decides, irrespective of the node from which it received a packet, the next node to which the packet should be forwarded. In some instances this can give rise to a “loop”. In particular this can occur when the databases (and corresponding forwarding information) are temporarily de-synchronized during a routing transition, that is, where because of a change in the network, a new LSP is propagated that induces creating a loop in the RIB or FIB. As an example, if node A sends a packet to node Z via node B, comprising the optimum route according to its SPF, a situation can arise where node B, according to its SPF determines that the best route to node Z is via node A and sends the packet back. This can continue for as long as the loop remains although usually the packet will have a maximum hop count after which it will be discarded. Such a loop can be a direct loop between two nodes or an indirect loop around a circuit of nodes.
One solution that has been proposed to the looping problem is described in co-pending patent application Ser. No. 11/064,275, filed Feb. 22, 2005, entitled “Method and Apparatus for Constructing a Repair Path Around a Non-Available Component in a Data Communications Network” of Michael Shand et al, (“Shand et al”), the entire contents of which are incorporated by reference for all purposes as is fully set forth herein and discussed in more detail below.
According to the solution in Shand et al a method for constructing a repair path can be understood with reference to FIG. 1 which depicts an illustrative network diagram to which the method is applied. The network includes a primary node P, reference numeral 200, a source node S, and nodes, A, B and C, reference numerals 202, 204, 206, 208 each connected to node P via respective links 210, 212, 214, 216. A further node D, reference numeral 218 is connected to node B via link 220. In addition to the standard addresses assigned to each node, each interface in the network is assigned an additional repair address. This is termed here the “notvia address” although it will be appreciated that this term is arbitrary, descriptive and non-limiting. The semantics of a notvia address are that a packet addressed to a notvia address must be delivered to the router with that address, notvia the neighboring router on the interface to which that address is assigned.
For example the interfaces from node P to nodes S, A, B, C by respective links 210, 212, 214, 216, may have addresses Pā, P b, P c and P s. Similarly the interfaces from nodes A, B, C and S to node P via links 212, 214, 216, 210 respectively in the opposite direction have addresses A p, B p, C p, S p.
To repair a failure, a repairing node, for example node S, encapsulates the packet to the notvia address of the node interface on the far side of the failure. The nodes on the repair path then know to which node they must deliver the packet, and which network component they must avoid.
Referring to FIG. 1, assuming that S has a packet for some destination D that it would normally send via P and B, and that S suspects that P has failed, S encapsulates the packet to B p. The path from S to B p is, according to the semantic the shortest path from S to B not going via P. If the network contains a path from S to B that does not transit router P, then the packet will be successfully delivered to B. For example the packet may be forwarded along path 222 to node X, 224, and then path 226 to node D. Because node X has calculated a repair path for B p it will forward the encapsulated packet correctly. When the packet addressed to B p arrives at B, B removes the encapsulation and forwards the repaired packet towards its final destination, node D.
This can be further understood with reference to FIG. 2 which is a flow diagram illustrating at a high level the method applied herein. In block 300 node P advertises, using a notification such as an LSP, its adjacencies A, B, C, S and its associated notvia addresses Pā, P b, P c, P s. It will be appreciated that all other nodes, acting as notifying node will also issue similar LSPs. As a result not only can appropriate forwarding tables be constructed, but also notvia addresses are available for each node in the event that it fails or otherwise becomes a non-available node, in which case the notvia address can be used as the repair address. Accordingly, in block 302, all participating nodes compute their next hops not only for each normal (non-failed) address but also for each notvia address. As a result each node constructs a repair path around each other node in the network and stores it against the corresponding notvia address.
In the event that node P subsequently fails or otherwise becomes unavailable, in block 304, then in block 306 the neighbour nodes detect or are notified of the failure in any appropriate manner. Where a neighbour node subsequently receives a packet which it would have sent to the failed component as its next hop then, acting as a repairing node, it identifies a repair end point or target to which it must tunnel such a packet to reach its subsequent destination in block 308. In the example given above, the repairing node is node S, and repair end point is node B for a packet with destination D. In particular this is identified by the respective notvia address B p. As a result the node S tunnels the packet along the repair path to B p in block 310. In block 312 each next hop forwards the encapsulated packet towards the notvia address B p, for example node X in FIG. 1 forwards the packet correctly. Because all of the participating nodes have calculated a path to the notvia address using the same repair topology, a packet is forwarded using normal IP forwarding without the requirement for extensions to the forwarding code. In block 314 the packet arrives at the repair end point which decapsulates it and forwards the original packet towards its destination, again using normal IP forwarding for destination D in the example described.
Referring once again to FIG. 1, it will be seen that in order to allow each enabled node on the network to construct a repair topology for a failed network component (link or node) each node must advertise its notvia addresses as well as the other relevant information stored in its LSP. Referring to FIG. 3, which is a diagram showing schematically the information contained in an LSP issued by node P, it will be seen that in addition to advertisement of each neighbour and its associated metric (e.g. the cost associated with the respective link) further information is provided. For example where the neighbour information is provided in column 400 and the associated metric in column 402, in addition a notvia address for each neighbour is provided in column 404. The notvia address is associated with the respective neighbour such that the entry against neighbour A effectively designates Pā. As long as the semantic is recognized by nodes receiving the LSP then the notvia address itself can take the form of a standard IP address shown schematically here as a.a.a.a representing Pā and so forth. It will be seen that, as every node in the network provides similar information, each node can derive repair paths for every notvia address on the network.
As a result, referring once again to the example described with reference to FIG. 1 in which node S encapsulates a packet destined for node D to P b in the event of failure of node P, every node more generally calculates the path it would use in the event of any possible node failure. Each node therefore fails every other router in the network, one at a time, and calculates its own best route to each of the neighbours of that node. In other words, again with reference to FIG. 1, some router X will consider each router in turn to be P, fail P, and then calculate its own route to each of the notvia IP addresses advertised by the neighbours of P. i.e. X calculates its route to S p, A p, B p and C p, in each case, notvia P.
Accordingly, referring to FIG. 4 which is a diagram illustrating relevant parts of the forwarding table derived at node S, it will be seen that for each address (column 500) the next hop (column 502) is derived, a notvia address (column 504) is designated and a corresponding repair address (column 506) is also implemented. For example where the destination is node B and the next hop is calculated as node P then, in addition, the repair address B p to which the packet will be tunneled is stored together with the corresponding repair next hop. In this case this is the first hop along the path 222 from node S to node X in the example described above with reference to FIG. 1, indicated as node Z, reference numeral 228 along link 230 from node S. In the case of packets destined for node D, the normal next hop is node P and the repair address is B p as a result of which the repair next hop is once again node Z for packets encapsulated to B p. In the case of node A as destination address, the next hop is node P and the repair address is A p providing some repair next hop Ω1 (not shown). The repair addresses in node S's forwarding table will always be to a neighbour's neighbour, ie the repair tunnel endpoint. However it will be seen that where the normal address in column 500 is a notvia address, for example C p, then although a next hop is provided as node Y, reference numeral 232 along link 234 from node S, a repair address and repair next hop are not provided as described in more detail below. As a result, node S will forward a packet using normal forwarding to a notvia address, when it lies in another node's repair path, but will not instigate a repair tunneled to a notvia address when the incoming packet is already destined for a notvia address.
One network configuration addressed in Shand et al is that of shared risk link groups (SRLG). An SRLG is a set of links whose failure can be caused by a single action such as a conduit cut or line card failure. When repairing the failure of a link that is a member of an SRLG, it must be assumed that all the other links that are also members of the SRLG have also failed, that is to say, the members of the SRLG comprise a group of components commonly renderable non-available. Consequently, any repair path must be computed to avoid not just the adjacent link, but also all the links which are members of the same SRLG.
According to the solution in Shand et al a repair path is computed and installed to the far side of all elements of the SRLG, encapsulating a repair packet to the notvia address of the router or node which has the lowest cost route from the repairing node to the destination. FIG. 5 is a network diagram illustrating the treatment of an SRLG in Shand et al including nodes A, B, C, D reference numerals 520, 522, 524, 526 respectively connected sequentially by links 528, 530, 532. Links 528 and 532 joining nodes AB and CD respectively belong to an SRLG S1. According to Shand et al in order to repair a failure of link 528 joining nodes AB, all components in the common SRLG, that is link 532 joining nodes C and D as well, are treated as failed and a repair path is constructed from node A to node D in a repair topology omitting those links and using further links and nodes in the topology which are not shown in FIG. 5. As a result traffic destined for destinations reachable via node D would be repaired to node D “notvia SRLG S1”. Traffic that needs to go to node B for example because some destinations such as node C are only reachable via node D are repaired to node B “notvia SRLG S1”. However it is found that this approach is unnecessarily conservative and results in an overly complex calculation; and in some cases repair destinations that are in fact available may be unreachable.